package leetcode.dp;

/**
 给定一个由 0 和 1 组成的矩阵 mat，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

 两个相邻元素间的距离为 1 。


 */
public class UpdateMatrix542 {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        //表示从[0,0]到[i,j]的最小和
        int [][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(mat[i][j]!=0)
                    dp[i][j] = 200001;
            }
        }
        //从左上开始
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(dp[i][j] ==0)
                    continue;
                if(i-1>=0)
                    dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j]);//上边
                if(j-1>=0)
                    dp[i][j] = Math.min(dp[i][j-1]+1,dp[i][j]);//左边
            }
        }

        //从右下开始
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if(dp[i][j] ==0)
                    continue;
                if(i+1<m)
                    dp[i][j] = Math.min(dp[i+1][j]+1,dp[i][j]);//下边
                if(j+1<n)
                    dp[i][j] = Math.min(dp[i][j+1]+1,dp[i][j]);//右边
            }
        }

        return  dp;
    }

    public static void main(String[] args) {
        int a = Integer.MAX_VALUE;
        int b = Integer.MAX_VALUE;
        System.out.println(Math.min(a,b));
    }

}